package com.demo.java.OD251_300.OD294;

import java.util.*;
import java.util.stream.*;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【AI 处理器组合】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146087602
 */
public class OdMain {
    // 深度优先搜索（DFS）回溯法，用于生成子集
    public static void dfs(List<Integer> nums, int index, int level, List<Integer> path, List<List<Integer>> subsets) {
        // 当路径长度等于目标要求的长度时，加入结果集
        if (path.size() == level) {
            subsets.add(new ArrayList<>(path));
        }

        // 从当前位置开始尝试每个元素
        for (int i = index; i < nums.size(); i++) {
            path.add(nums.get(i));  // 选择当前元素
            dfs(nums, i + 1, level, path, subsets);  // 递归选择下一个元素
            path.remove(path.size() - 1);  // 回溯，撤销选择
        }
    }

    // 根据目标选择不同的处理器组合
    public static String findSubsets(List<Integer> nums, String target) {
        // 将处理器编号分为两组
        List<Integer> smallNums = new ArrayList<>();
        List<Integer> largeNums = new ArrayList<>();

        // 分类：小于4的处理器到smallNums，大于等于4的处理器到largeNums
        for (Integer num : nums) {
            if (num < 4) {
                smallNums.add(num);
            } else {
                largeNums.add(num);
            }
        }

        // 记录所有符合条件的子集
        List<List<Integer>> subsets = new ArrayList<>();
        int smallSize = smallNums.size();
        int largeSize = largeNums.size();

        // 根据目标值选择不同的处理器数量
        switch (target) {
            case "1":
                handleTarget1(smallNums, largeNums, smallSize, largeSize, subsets);
                break;
            case "2":
                handleTarget2(smallNums, largeNums, smallSize, largeSize, subsets);
                break;
            case "4":
                handleTarget4(smallNums, largeNums, smallSize, largeSize, subsets);
                break;
            case "8":
                handleTarget8(smallNums, largeNums, smallSize, largeSize, subsets);
                break;
        }

        // 返回符合条件的组合
        return subsets.toString();
    }

    // 处理目标值为1的情况
    public static void handleTarget1(List<Integer> smallNums, List<Integer> largeNums, int smallSize, int largeSize, List<List<Integer>> subsets) {
        if (smallSize == 1 || largeSize == 1) {
            if (smallSize == 1) dfs(smallNums, 0, 1, new ArrayList<>(), subsets);
            if (largeSize == 1) dfs(largeNums, 0, 1, new ArrayList<>(), subsets);
        } else if (smallSize == 3 || largeSize == 3) {
            if (smallSize == 3) dfs(smallNums, 0, 1, new ArrayList<>(), subsets);
            if (largeSize == 3) dfs(largeNums, 0, 1, new ArrayList<>(), subsets);
        } else if (smallSize == 2 || largeSize == 2) {
            if (smallSize == 2) dfs(smallNums, 0, 1, new ArrayList<>(), subsets);
            if (largeSize == 2) dfs(largeNums, 0, 1, new ArrayList<>(), subsets);
        } else if (smallSize == 4 || largeSize == 4) {
            if (smallSize == 4) dfs(smallNums, 0, 1, new ArrayList<>(), subsets);
            if (largeSize == 4) dfs(largeNums, 0, 1, new ArrayList<>(), subsets);
        }
    }

    // 处理目标值为2的情况
    public static void handleTarget2(List<Integer> smallNums, List<Integer> largeNums, int smallSize, int largeSize, List<List<Integer>> subsets) {
        if (smallSize == 2 || largeSize == 2) {
            if (smallSize == 2) dfs(smallNums, 0, 2, new ArrayList<>(), subsets);
            if (largeSize == 2) dfs(largeNums, 0, 2, new ArrayList<>(), subsets);
        } else if (smallSize == 4 || largeSize == 4) {
            if (smallSize == 4) dfs(smallNums, 0, 2, new ArrayList<>(), subsets);
            if (largeSize == 4) dfs(largeNums, 0, 2, new ArrayList<>(), subsets);
        } else if (smallSize == 3 || largeSize == 3) {
            if (smallSize == 3) dfs(smallNums, 0, 2, new ArrayList<>(), subsets);
            if (largeSize == 3) dfs(largeNums, 0, 2, new ArrayList<>(), subsets);
        }
    }

    // 处理目标值为4的情况
    public static void handleTarget4(List<Integer> smallNums, List<Integer> largeNums, int smallSize, int largeSize, List<List<Integer>> subsets) {
        if (smallSize == 4 || largeSize == 4) {
            if (smallSize == 4) subsets.add(smallNums);
            if (largeSize == 4) subsets.add(largeNums);
        }
    }

    // 处理目标值为8的情况
    public static void handleTarget8(List<Integer> smallNums, List<Integer> largeNums, int smallSize, int largeSize, List<List<Integer>> subsets) {
        if (smallSize == 4 && largeSize == 4) {
            subsets.add(Stream.concat(smallNums.stream(), largeNums.stream())
                    .collect(Collectors.toList()));
        }
    }

    public static void main(String[] args) {
        try (Scanner scanner = new Scanner(System.in)) {
            List<Integer> nums = readIntegerList(scanner.nextLine());
            String target = scanner.next();
            System.out.println(findSubsets(nums, target));
        }
    }

    // 解析输入的处理器编号数组
    public static List<Integer> readIntegerList(String input) {
        return Arrays.stream(input.split("[\\[\\],\\s]"))
                .filter(str -> !str.isEmpty())
                .map(Integer::parseInt)
                .collect(Collectors.toList());
    }
}